package com.itheima.algorithm.recursion;

import java.util.Arrays;

/**
 * 递归求斐波那契数列
 * 之前的例子是每个递归函数只包含一个自身的调用,这称之为single recursion
 * 如果每次递归函数包含多个自身调用，称之为多路递归
 */
public class Fibonacci {

    public static int fibonacci(int n){
        int [] cache = new int[n+1];

        Arrays.fill(cache,-1);
        cache[0] = 0;
        cache[1] = 1;
        return improveF(n,cache);
    }

    public static int improveF(int n,int [] cache){
        if(cache[n]!=-1){
            return cache[n];
        }
        int x = f(n-1);
        int y= f(n-2);
        // 存入数组
        cache[n] = x+y;
        return cache[n];
    }

    public static int f(int n){
        if(n==0){
            return 0;
        }
        if(n ==1){
            return 1;
        }
        int x = f(n-1);
        int y= f(n-2);
        return x+y;
    }

    public static void main(String[] args) {
        System.out.println(f(8));
        System.out.println(fibonacci (8));
    }


}
